class Solution {
public:
    bool queryString(string s, int n) {
        if(n==1) return s.find('1')!=string::npos;

        int m=s.size();
        int k=31-__builtin_clz(n);
        if(m<max(n-(1<<k)+k+1,(1<<(k-1))+k-1)) return false;

        auto check=[&](int k,int lower,int upper) ->bool
        {
            if(lower>upper) return true;
            unordered_set<int> seen;
            int mask=(1<<(k-1))-1;
            int x=stoi(s.substr(0,k-1),nullptr,2);
            for(int i=k-1;i<m;++i)
            {
                x=((x&mask)<<1)|(s[i]-'0');
                if(lower<=x&&x<=upper) seen.insert(x);
            }
            return seen.size()==upper-lower+1;
        };
        return check(k,n/2+1,(1<<k)-1)&&check(k+1,1<<k,n);
    }
    
    bool queryString(string s, int n) {
        unordered_set<int> seen;
        for(int i=0,m=s.size();i<m;++i)
        {
            int x=s[i]-'0';
            if(x==0) continue;
            for(int j=i+1;x<=n;++j)
            {
                seen.insert(x);
                if(j==m) break;
                x=(x<<1)|(s[j]-'0');
            }
        }
        return seen.size()==n;
    }
    
    bool queryString(string s, int n) {
        for(int i=1;i<=n;++i)
        {
            auto bin=bitset<32>(i).to_string();
            bin=bin.substr(bin.find('1'));
            if(s.find(bin)==string::npos) return false;
        }
        return true;
    }
};